Cơ sở đại số: Các đường thẳng và tập hợp affine
Để di chuyển trong một môi trường tối ưu nhiều chiều, chúng ta cần xác định cách di chuyển giữa hai điểm $x_1$ và $x_2$. Một đường thẳng toán học là tập hợp tất cả các điểm $y$ thỏa mãn:
$$y = \theta x_1 + (1 - \theta)x_2$$
Tương đương, ta có thể xem đây là xuất phát từ $x_2$ và di chuyển theo hướng $(x_1 - x_2)$ với hệ số mở rộng $\theta$: $y = x_2 + \theta(x_1 - x_2)$. Khi $\theta$ thay đổi trên mọi số thực $\mathbb{R}$, ta tạo thành một tập hợp affine. Một thuộc tính quan trọng cần nhớ: Mọi đường thẳng đều là tập affine. Nếu nó đi qua gốc tọa độ, thì nó là một không gian con, do đó cũng là một nón lồi.
Một đoạn thẳng là giới hạn khi $0 \le \theta \le 1$. Khác với đường thẳng vô hạn, một đoạn thẳng là lồi, nhưng không phải affine (trừ khi nó suy biến thành một điểm). Nó biểu diễn tập hợp tất cả các "trung bình có trọng số" hoặc sự pha trộn giữa hai đầu mút.
Một tia, có dạng $\{x_0 + \theta v \mid \theta \ge 0\}$, với $v \neq 0$, cũng là lồi, nhưng không phải affine. Các tia là những khối xây dựng cơ bản cho các nón trong lý thuyết tối ưu.
Thử nghiệm tính lồi
Chúng ta định nghĩa một tập hợp $C$ là lồi nếu đoạn thẳng nối bất kỳ hai điểm nào trong tập hợp đều nằm hoàn toàn bên trong tập hợp. Yêu cầu đơn giản này – việc bao gồm "cầu nối" – chính là yếu tố quyết định việc các bài toán tối ưu có thể giải được hay không.
Ví dụ: Tối ưu danh mục đầu tư
Trong tài chính, giả sử $x_1$ biểu thị một danh mục đầu tư 100% cổ phiếu và $x_2$ là 100% trái phiếu. Đoạn thẳng biểu diễn tất cả các tỷ lệ pha trộn có thể. Chẳng hạn, tỷ lệ 60/40 xảy ra tại $\theta = 0.6$. Nếu tập hợp các "danh mục được phép" là lồi, thì bất kỳ sự pha trộn nào giữa hai danh mục hợp lệ cũng sẽ luôn là hợp lệ – một tính chất giúp đơn giản hóa đánh giá rủi ro một cách đáng kể.